package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;

/**206. 反转链表 https://leetcode-cn.com/problems/reverse-linked-list/
 * @author 60906
 * @date 2021/5/4 21:58
 */
public class Q_反转链表 {

    public static void main(String[] args) {
        Solution s1 = new Solution();
        Solution_2 s2 = new Solution_2();
        LinkNode head1 = LinkNode.toListNode(1, 2, 3, 4, 5);
        LinkNode head2 = LinkNode.toListNode(1, 2, 3, 4, 5);
        LinkNode r1 = s1.reverseList(head1);
        LinkNode r2 = s2.reverseList(head2);
        r1.print();
        r2.print();
    }

    /**
     * 迭代
     */
    private static class Solution {

        public LinkNode reverseList(LinkNode head) {
            if (head==null) {
                return head;
            }
            LinkNode prev = null;
            LinkNode cur = head;
            LinkNode next = null;
            while (cur != null) {
                next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }

            return prev;
        }
    }

    /**
     * 递归
     */
    private static class Solution_2 {

        public LinkNode reverseList(LinkNode head) {
            // head null 时, 是原始数据边界条件, 递归不会出现
            if (head == null || head.next == null) {
                return head; // 我就是翻转后的头
            }

            // 递归将 next 及其后面的翻转, 并 "透返" 新的头节点
            LinkNode p = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            // "透返" (透传)
            return p;
        }

    }





    /**
     * 递归解法(我自己的, 太啰嗦了)
     * @deprecated
     */
    private static class Solution_2_dep {
        public LinkNode reverseList(LinkNode head) {
            return reverseList0(head)[0];
        }
        public LinkNode[] reverseList0(LinkNode head) {
            LinkNode[] info = new LinkNode[2];
            if (head==null) {
                return info;
            }
            // 头[0], 反转之后的尾子[1]
            info = reverseList0(head.next);
            if (info[1] != null) {
                info[1].next = head;
                head.next = null;
            } else {
                // 当前是旧的尾子==反转之后的头
                info[0] = head;
            }
            info[1] = head;
            return info;
        }
    }
}
